package com.leet.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Zifuchuandepailie38 {
    List<String> ans = new ArrayList<>();
    public void backTracking(String s,StringBuilder tmp,boolean[] vis){
        if(s.length() == tmp.length()){
            ans.add(tmp.toString());
            return;
        }
        for(int i = 0; i < s.length(); i++){
            // 如果i已经访问过，或者前后两项相同且前面的已经访问过（i>0)
            if(vis[i]||(i > 0 && !vis[i - 1] && s.charAt(i-1) == s.charAt(i))) continue;
            vis[i] = true;
            tmp.append(s.charAt(i));
            backTracking(s,tmp,vis);
            tmp.deleteCharAt(tmp.length()-1);
            vis[i] = false;
        }
    }
    public String[] permutation(String s) {
        ans.clear();
        StringBuilder tmp = new StringBuilder();
        boolean[] vis = new boolean[s.length()];
        char[] sChar = s.toCharArray();
        Arrays.sort(sChar);
        String s1 = new String(sChar);
        backTracking(s1,tmp,vis);
        int n = ans.size();
        String[] res = new String[n];
        for(int i = 0; i < n; i++){
            res[i] = ans.get(i);
        }
        return res;
    }
}
